Systems in which many devices share a common resource typically utilize arrangements for allocating access to the resource under conditions during which a plurality of associated devices may concurrently request access. Many different allocation arrangements are known in the art. In data processing and packet switching systems, it is known to use a centralized allocator or controller for allocating access to a common data bus interconnecting a plurality of units, such as ports, that may concurrently request access to the bus. The controller may be programmed with an appropriate algorithm to allocate bus access in accordance with any priorly determined criterion that may be desired. Although centralized controller allocation arrangements operate suitably to perform their intended function, they are not always desirable because of the inherent system complexity resulting from the many interconnections required between the controller, the bus, and the ports. Also, a reliability problem exists since a malfunction of the controller may remove the whole system from operation. A system having a centralized controller is shown by U.S. Pat. No. 3,983,540 issued Sept. 28, 1976 to Keller et al.
It is known to use distributed bus allocation arrangements in which a controller is not used to determine access and instead, the interaction of the requesting ports determines bus allocation in the event of simultaneous requests. Such distributed arrangements are often preferable since the expense of and the reliability problems associated with the centralized controller arrangement are avoided.
In accordance with one such distributed allocation arrangement, each port that may request access to a common bus is assigned a fixed priority number comprising a plurality of binary digits. Access is granted by priority number in case of concurrent requests. During bus contention time, when two or more ports concurrently request access, each requesting port applies the corresponding bits of its priority number to an arbitration bus sequentially, bit by bit, in synchronism with the application of corresponding bits by all other concurrently requesting ports. As each bit is applied, each bidding port compares the magnitude of the bit it is currently applying with the logical union of the corresponding bits applied simultaneously to the arbitration bus by all concurrently requesting ports. If a bit one requesting port currently applies has a prescribed relationship (such as equal to or higher) to the bits applied to the bus by the other requesting ports, this operation proceeds and the port applies the next bit of its assigned priority number to the arbitration bus.
Each port stays in contention as long as each bit it applies has the prescribed relationship to the logical union of the corresponding bits currently applied by other contending ports. A port removes itself from contention when it determines that a bit it applies has a relationship (such as is lower than) to the bits currently applied by the other ports indicating that one or more of the other ports has a higher priority number. At that time, each port having a lower priority number removes itself from contention and applies no further bits to the bus.
This contention operation continues; the remaining bits of the port priority numbers are applied to the bus by all remaining requesting ports; ports of a lower priority remove themselves from contention; and at the end of the contention interval when the last bit is applied to the bus, only the port having the highest priority remains in contention and it is granted access to the bus. An arrangement of the above described type is shown in U.S. Pat. No. 3,796,992 issued Mar. 12, 1974, to Nakamura et al and in U.S. Pat. No. 3,818,447 issued June 18, 1974 to Craft.
The above described distributed contention arrangement operates satisfactory. However, it suffers from the disadvantage that the port priority numbers are fixed and, since port access is determined by these numbers, the ports may be considered to be functionally arranged in a fixed preference chain with the most preferred port having the highest priority number and the least preferred port having the lowest priority number. This being the case, access to the bus is not equitable since ports having the higher priority numbers are always favored in the event of simultaneous requests. While this unequitable allocation of ports may be tolerable in certain systems, it is a disadvantage in those systems in which more equitable access by all ports is required.